package com.leetcode.solution.s7x;

import java.util.ArrayList;
import java.util.List;

public class Subsets {
    public static void main(String[] args) {
        List<List<Integer>> result = new Subsets().subsets(new int[] {1, 2, 3});

        for (List<Integer> integers : result) {
            for (Integer integer : integers) {
                System.out.print(integer + ",");
            }
            System.out.println("");
        }
    }

    public List<List<Integer>> subsets(int[] nums) {
        return nextSubsets(nums, 0);
    }

    private List<List<Integer>> nextSubsets(int[] nums, int idx) {
        List<List<Integer>> subsets = new ArrayList<>();
        List<Integer> tmp;
        if (idx == nums.length - 1) {
            tmp = new ArrayList<>();
            subsets.add(tmp);

            tmp = new ArrayList<>();
            tmp.add(nums[idx]);
            subsets.add(tmp);
        } else {
            List<List<Integer>> nextSubsets = nextSubsets(nums, idx + 1);
            for (List<Integer> nextSubset : nextSubsets) {
                subsets.add(nextSubset);
                tmp = new ArrayList<Integer>(nextSubset);
                tmp.add(nums[idx]);
                subsets.add(tmp);
            }
        }

        return subsets;
    }
}
